DAY 28 試題

問題描述

給定一個整數陣列 nums，請返回「最長嚴格遞增子序列」的長度。子序列是指從陣列中提取的一部分元素，並且這些元素的相對順序保持不變，但不需要是連續的。

範例 1：

• 輸入：nums = [10,9,2,5,3,7,101,18]
• 輸出：4
• 解釋：最長的遞增子序列是 [2,3,7,101]，因此長度為 4。

範例 2：

• 輸入：nums = [0,1,0,3,2,3]
• 輸出：4

範例 3：

• 輸入：nums = [7,7,7,7,7,7,7]
• 輸出：1

限制條件：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

解題思路

這道題要求找到最長的「嚴格遞增子序列」的長度。解法可以分為兩種常見的方法：

動態規劃法：

• 我們可以使用動態規劃來求解，時間複雜度為 O(n^2)。
• 定義一個長度為 n 的陣列 dp，其中 dp[i] 代表以 nums[i] 結尾的最長遞增子序列的長度。
• 我們可以通過遍歷 nums，對每個位置 i，檢查之前的每個位置 j，如果 nums[j] < nums[i]，則更新 dp[i] 為 dp[j] + 1。
• 最後結果為 dp 陣列中的最大值。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int n = nums.size();
        vector<int> dp(n, 1); // 初始化每個元素的最長遞增子序列長度為 1
        int max_len = 1;  // 用來追蹤最長遞增子序列的長度
        
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_len = max(max_len, dp[i]);  // 更新全局最大值
        }
        
        return max_len;
    }
};

二分查找法（O(n log n) 解法）：

• 使用一個輔助數組 tails 來維護目前最小的可能結尾值。
• 遍歷每個元素，使用二分查找將元素插入到 tails 中合適的位置，如果元素比 tails 中所有值都大，就將其添加到 tails 的尾部。
• 這樣可以確保 tails 的長度是當前的最長遞增子序列長度。
• 這種方法的時間複雜度為 O(n log n)，適合長度較大的輸入。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;  // 用來存放遞增子序列的尾部元素
        for (int num : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), num);
            if (it == tails.end()) {
                tails.push_back(num);  // 將 num 添加到尾部
            } else {
                *it = num;  // 用 num 替換當前位置
            }
        }
        return tails.size();  // tails 的大小就是最長遞增子序列的長度
    }
};

解法重點與分析

1. 動態規劃法：

• 我們使用動態規劃陣列 dp 來記錄每個位置的最長遞增子序列長度。
• 每個位置的狀態由之前的結果決定，因此時間複雜度為 O(n^2)。
• 雖然時間複雜度較高，但概念較為簡單。

2. 二分查找法：

• 使用二分查找來加速元素的插入過程。通過維護一個最小結尾值的列表 tails，可以在 O(n log n) 的時間內解決問題。
• 這種方法更適合處理大型輸入。

複雜度分析

1. 動態規劃法：

• 時間複雜度：O(n^2)，因為對於每個元素，我們需要檢查其之前的所有元素。
• 空間複雜度：O(n)，需要一個大小為 n 的陣列來存儲動態規劃結果。

2. 二分查找法

• 時間複雜度：O(n log n)，我們使用二分查找來找到合適的位置插入每個元素。
• 空間複雜度：O(n)，需要一個大小為 n 的輔助數組 tails。

總結

這題可以通過兩種方法來解決，動態規劃法雖然時間複雜度較高，但思路清晰；而二分查找法則優化了時間複雜度，適合處理更大的數據集。通過這兩種方法，可以靈活應對不同場景下的最長遞增子序列問題。

以上是第二十八天的自學內容分享，謝謝大家。